package array.sliding_window;
import java.util.Scanner;
//此题属于动态规划
public class lc5 {
    public static void main(String[] args) {
        String s="babad";
        System.out.println(longestPalindrome(s));

    }
    public static String longestPalindrome(String s) {
        char[] chars=s.toCharArray();
        int maxleft=0;
        int maxright=0;
        int left=0;
        int right=1;
        int maxlength=1;
        int curlength=0;
        while(right<s.length()){
            curlength=right-left+1;
            while(isPalindrome(s.substring(left,right+1))){
                left++;
                if(curlength>maxlength){
                    maxlength=curlength;
                    maxleft=left;
                    maxright=right;
                }
            }
            right++;

        }
        return s.substring(maxleft,maxright+1);

    }
    public static boolean isPalindrome(String s){
        //true 是回文
        char[] chars=s.toCharArray();
        if(s.length()==1){
            return true;
        }
        if(s.length()==2){
            if(chars[0]==chars[1]) return true;
            return false;
        }
        if(s.length()==3){
            if(chars[0]==chars[2]) return true;
            return false;
        }
        int j=0;
        for (j = 0; j <s.length()*0.5 ; j++) {
            if(chars[j]!=chars[s.length()-1-j]){
                break;
            }
        }
        if(j!=s.length()*0.5-1){
            return false;
        }
        return true;
    }
}
